1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
|
// SPDX-FileCopyrightText: Copyright 2022 yuzu Emulator Project
// SPDX-License-Identifier: GPL-2.0-or-later
#pragma once
#include <span>
#include <vector>
#include "audio_core/renderer/nodes/edge_matrix.h"
#include "common/alignment.h"
#include "common/common_types.h"
namespace AudioCore::Renderer {
/**
* Graph utility functions for sorting and getting results from the DAG.
*/
class NodeStates {
/**
* State of a node in the depth first search.
*/
enum class SearchState {
Unknown,
Found,
Complete,
};
/**
* Stack used for a depth first search.
*/
struct Stack {
/**
* Calculate the workbuffer size required for this stack.
*
* @param count - Maximum number of nodes for the stack.
* @return Required buffer size.
*/
static u32 CalcBufferSize(u32 count) {
return count * sizeof(u32);
}
/**
* Reset the stack back to default.
*
* @param buffer_ - The new buffer to use.
* @param size_ - The size of the new buffer.
*/
void Reset(u32* buffer_, u32 size_) {
stack = {buffer_, size_};
size = size_;
pos = 0;
unk_10 = size_;
}
/**
* Get the current stack position.
*
* @return The current stack position.
*/
u32 Count() const {
return pos;
}
/**
* Push a new node to the stack.
*
* @param data - The node to push.
*/
void push(u32 data) {
stack[pos++] = data;
}
/**
* Pop a node from the stack.
*
* @return The node on the top of the stack.
*/
u32 pop() {
return stack[--pos];
}
/**
* Get the top of the stack without popping.
*
* @return The node on the top of the stack.
*/
u32 top() const {
return stack[pos - 1];
}
/// Buffer for the stack
std::span<u32> stack{};
/// Size of the stack buffer
u32 size{};
/// Current stack position
u32 pos{};
/// Unknown
u32 unk_10{};
};
public:
/**
* Calculate the workbuffer size required for the node states.
*
* @param count - The number of nodes.
* @return The required workbuffer size.
*/
static u64 GetWorkBufferSize(u32 count) {
return (Common::AlignUp(count, 0x40) / sizeof(u64)) * 2 + count * sizeof(BitArray) +
count * Stack::CalcBufferSize(count);
}
/**
* Initialize the node states.
*
* @param buffer_ - The workbuffer to use. Unused.
* @param node_buffer_size - The size of the workbuffer. Unused.
* @param count - The number of nodes in the graph.
*/
void Initialize(std::span<u8> buffer_, u64 node_buffer_size, u32 count);
/**
* Sort the graph. Only calls DepthFirstSearch.
*
* @param edge_matrix - The edge matrix used to hold the connections between nodes.
* @return True if the sort was successful, otherwise false.
*/
bool Tsort(const EdgeMatrix& edge_matrix);
/**
* Sort the graph via depth first search.
*
* @param edge_matrix - The edge matrix used to hold the connections between nodes.
* @param stack - The stack used for pushing and popping nodes.
* @return True if the sort was successful, otherwise false.
*/
bool DepthFirstSearch(const EdgeMatrix& edge_matrix, Stack& stack);
/**
* Get the search state of a given node.
*
* @param id - The node id to check.
* @return The node's search state. See SearchState
*/
SearchState GetState(u32 id) const;
/**
* Push a node id to the results buffer when found in the DFS.
*
* @param id - The node id to push.
*/
void PushTsortResult(u32 id);
/**
* Set the state of a node.
*
* @param id - The node id to alter.
* @param state - The new search state.
*/
void SetState(u32 id, SearchState state);
/**
* Reset the nodes found, complete and the results.
*/
void ResetState();
/**
* Get the number of nodes in the graph.
*
* @return The number of nodes.
*/
u32 GetNodeCount() const;
/**
* Get the sorted results from the DFS.
*
* @return Vector of nodes in reverse order.
*/
std::pair<std::span<u32>::reverse_iterator, size_t> GetSortedResuls() const;
private:
/// Number of nodes in the graph
u32 node_count{};
/// Position in results buffer
u32 result_pos{};
/// List of nodes found
BitArray nodes_found{};
/// List of nodes completed
BitArray nodes_complete{};
/// List of results from the depth first search
std::span<u32> results{};
/// Stack used during the depth first search
Stack stack{};
};
} // namespace AudioCore::Renderer
|
